package pers.qianyu.month_202101.date_20210123;

import java.util.*;

/**
 * 692. 前K个高频单词
 * https://leetcode-cn.com/problems/top-k-frequent-words/
 *
 * @author mizzle rain
 * @date 2021-01-23 11:23
 */
public class TopKFrequent {
    private static class Pair implements Comparable<Pair> {
        private String key;
        private int value;

        public String getKey() {
            return key;
        }

        public void setKey(String key) {
            this.key = key;
        }

        public int getValue() {
            return value;
        }

        public void setValue(int value) {
            this.value = value;
        }

        public Pair(String key, int value) {
            this.key = key;
            this.value = value;
        }

        @Override
        public boolean equals(Object o) {
            if (this == o) return true;
            if (o == null || getClass() != o.getClass()) return false;

            Pair pair = (Pair) o;

            if (value != pair.value) return false;
            return key != null ? key.equals(pair.key) : pair.key == null;
        }

        @Override
        public int hashCode() {
            int result = key != null ? key.hashCode() : 0;
            result = 31 * result + value;
            return result;
        }

        @Override
        public int compareTo(Pair p1) {
            if (this.value != p1.getValue()) {
                return this.value - p1.getValue();
            }
            // ASCII 值越小，它的字典序就越大
            return p1.getKey().compareTo(this.key);
        }
    }

    public List<String> topKFrequent(String[] words, int k) {
        HashMap<String, Integer> map = new HashMap<>();
        for (String word : words) {
            map.put(word, map.getOrDefault(word, 0) + 1);
        }
        PriorityQueue<Pair> q = new PriorityQueue<>();
        for (String key : map.keySet()) {
            int value = map.get(key);
            Pair pair = new Pair(key, value);
            if (q.size() == k) {
                if (q.peek().compareTo(pair) < 0) {
                    q.poll();
                    q.add(pair);
                }
            } else {
                q.add(pair);
            }
        }

        ArrayList<String> res = new ArrayList<>();
        while (!q.isEmpty()) {
            res.add(q.poll().getKey());
        }
        Collections.reverse(res);
        return res;
    }

    public static void main(String[] args) {
        System.out.println("i".compareTo("love"));
    }
}
